%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction to Cryptography}
\label{chap:introduction_cryptography}

\emph{Cryptography} is the study of mathematical techniques for all
aspects of information security.  \emph{Cryptanalysis} is the
complementary science concerned with the methods to defeat these
techniques.  \emph{Cryptology} is the study of cryptography and
cryptanalysis.  Key features of information security include
\emph{confidentiality} or \emph{privacy}, \emph{data integrity},
\emph{authentication}, and \emph{nonrepudiation}.

Each of these aspects of message security can be addressed by standard
methods in cryptography.  Besides exchange of messages, tools from
cryptography can be applied to sharing an access key between multiple
parties so that no one person can gain access to a vault by any two
of them.  Another role is in the design of electronic forms of cash.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Definitions and examples}

The following definitions will be used throughout the book.

\begin{description}
\item[encryption] The process of disguising a message so as to hide
  the information it contains. This process can include both encoding
  and enciphering~(see definitions below).

\item[protocol] An algorithm, defined by a sequence of steps,
  precisely specifying the actions of multiple parties in order to
  achieve an objective.

\item[plaintext] The message to be transmitted or stored.

\item[ciphertext] The disguised message.

\item[alphabet] A collection of symbols, also referred to as characters.

\item[character] An element of an alphabet.

\item[bit] A character $0$ or $1$ of the binary alphabet.

\item[string] A finite sequence of characters in some alphabet.

\item[encode] To convert a message into a representation in a standard
  alphabet, such as the alphabet $\{\tA,\dots,\tZ\}$ or the numerical
  alphabet.

\item[decode] To convert the encoded message back to its original
  alphabet and original form. The term plaintext will apply to either
  the original or the encoded form.  The process of encoding a message
  is not an obscure process, and the result that we get can be
  considered equivalent to the plaintext message.

\item[cipher] A map from a space of plaintext to a space of ciphertext.

\item[encipher] To convert plaintext into ciphertext.

\item[decipher] To convert ciphertext back to plaintext.

\item[stream cipher] A cipher that acts on the plaintext one symbol
  at a time.

\item[block cipher] A cipher that acts on the plaintext in blocks of
  symbols.

\item[substitution cipher] A stream cipher that acts on the plaintext
  by making a substitution of the characters with elements of a new
  alphabet or by a permutation of the characters in the plaintext
  alphabet.

\item[transposition cipher] A block cipher that acts on the plaintext
  by permuting the positions of the characters in the plaintext.
\end{description}

\begin{table}[!htbp]
\centering
\input{data/introduction/standard-alphabets.tex}
\caption{Standard alphabets in cryptology.}
\label{tab:introduction:standard_alphabets}
\end{table}

\begin{example}
\rm
Table~\ref{tab:introduction:standard_alphabets} lists some standard
alphabets. Some of these alphabets often occur in cryptology. \qed
\end{example}

\begin{example}
\rm
The following is an example of a substitution cipher:
\[
\begin{array}{lllllllllll}
\tA & \tB & \tC & \tD & \tE & \tF & \tG & \tH & \cdots & \tZ & \un \\
\da & \da & \da & \da & \da & \da & \da & \da & \cdots & \da & \da \\
\tP & \tC & \un & \tO & \tN & \tA & \tW & \tY & \cdots & \tL & \tS \\
\end{array}
\]
where the underscore character ``\un'' denotes a single white
space. Using the above cipher, the plaintext \texttt{BAD CAFE BED} is
transformed into the ciphertext \texttt{CPOS PANSCNO}. \qed
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{String monoids}

An encoding or cipher is a transformation of data or text, whether
expressed in the Roman alphabet, Chinese characters, or some binary,
hexadecimal, or byte encoding of this information.  We present here
some of the structures in which this text is stored, as the natural
domain and codomain on which encodings and ciphers operate. First, we
present the abstract notion of a monoid before specializing to the
string monoids, which form the objects of interest.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Monoids}

A \emph{semigroup} is a set $\cM$ together with a binary operation
\[
\cdot\ : \cM \times \cM \to \cM
\]
that is associative. That is, we have
\[
(x \cdot y) \cdot z
=
x \cdot (y \cdot z)
\]
for all $x,y,z \in \cM$.  A semigroup $\cM$ is said to be a
\emph{monoid} if it contains a distinguished element $e \in \cM$ such
that $e \cdot x = x = x \cdot e$ for all $x \in \cM$.  A monoid in
which every element $x \in \cM$ has an inverse element $y \in \cM$,
i.e.~such that $x \cdot y = e$, is called a \emph{group}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Monoid homomorphisms}

Let $\cM_1$ and $\cM_2$ be monoids. A \emph{monoid homomorphism} is a
map $\phi: \cM_1 \to \cM_2$ such that
\[
\phi(x \cdot y)
=
\phi(x) \cdot \phi(y)
\]
and which takes the identity in $\cM_1$ to the identity in $\cM_2$.
We denote the set of all monoid homomorphisms $\cM_1 \to \cM_2$ by
\[
\Hom_{\tt Mon}(\cM_1,\cM_2)
\]
or just $\Hom(\cM_1,\cM_2)$ when it is clear that $\cM_1$ and $\cM_2$
are both monoids.  In contrast, the set of all set-theoretic maps from
$\cM_1$ to $\cM_2$ is denoted
\[
\Hom_{\tt Set}(\cM_1,\cM_2).
\]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Strings}

Given a finite alphabet $\cA$ (a finite set of symbols), we write
$\cA^n$ for the $n$-fold product
\[
\underbrace{\cA \times \cA \times \cdots \times \cA}_{\text{$n$ copies of $\cA$}}
\]
whose elements we call \emph{strings} of length $n$. Let
\[
\cA^*
=
\bigcup_{n=0}^\infty \cA^n
\]
be the disjoint union over strings of all lengths.  Then $\cA^*$ forms
a monoid under string concatenation, with identity the unique string
in $\cA^0$ called the \emph{empty string} and denoted $\varepsilon$.
We identify $\cA$ with its image $\cA^1$ in $\cA^*$ and write a string
in $\cA^n$ as $x_1 x_2 \cdots x_n$ rather than $(x_1,x_2,\dots,x_n)$.

The string monoids $\cA^*$ form a very special class of monoids called
\emph{free monoids} over $\cA$, which are characterized by the
following ``universal'' property:
%%
\begin{center}
\begin{minipage}{135mm}
{\it
The set $\cA$ generates $\cA^*$. Given any map $\cA \to \cM$ to a
monoid $\cM$, there exists a unique monoid homomorphism
$\cA^* \to \cM$ which extends $\cA \to \cM$.}
\end{minipage}
\end{center}
%%
Since the length of strings adds when composing (i.e.~concatenating)
them, clearly no element other than the empty string in $\cA^*$ has an
inverse. Thus $\cA^*$ forms a monoid but not a group.

%% State this formally as a morphism from a string monoid to the additive
%% monoid of non-negative integers.

\begin{table}[!htbp]
\centering
\input{data/introduction/English-alphabet-ASCII-integers-binary.tex}
\caption{Correspondence between the English alphabet and ASCII
  integers and binary representations.}
\label{tab:introduction:English_alphabet_ASCII_integers_binary}
\end{table}

We are interested in standard string monoids used in language and
computers. For example, we let \texttt{ASCII} be the set of $256$
binary strings of length $8$, which represent text in the computer.
For instance,
Table~\ref{tab:introduction:English_alphabet_ASCII_integers_binary}
shows the correspondence between characters in the Roman alphabet,
numeric decimal values, and the binary representation of the ASCII
alphabet. Note that the space character "\ " is a valid symbol in the
ASCII alphabet, with numeric value 32.  In particular it is a symbol
distinct from the identity element of the monoid $\texttt{ASCII}^*$.

We now let $\cA$ be the alphabet consisting of the $26$ symbols
$\{\tA, \tB, \dots, \tZ\}$.  There is an obvious monoid homomorphism
$\iota: \cA^* \to \texttt{ASCII}^*$ induced by the inclusion
$\cA \subset \texttt{ASCII}$.  We can define a map
$\texttt{ASCII} \to \cA^*$ by extending the map
\[
\begin{array}{ccc}
\tA \mapsto \tA & \qquad & \ta \mapsto \tA \\
\tB \mapsto \tB &        & \tb \mapsto \tB \\
\vdots          &        & \vdots          \\
\tZ \mapsto \tZ &        & \tz \mapsto \tZ
\end{array}
\]
to all of {\tt ASCII} by sending all other characters to the empty
string $\varepsilon$. This induces a monoid homomorphism
$\pi: \texttt{ASCII}^* \to \cA^*$ such that the composition
$\iota \circ \pi$ is the identity homomorphism on $\cA^*$, but
$\pi \circ \iota$ is far from injective on $\texttt{ASCII}^*$.

This monoid homomorphism was commonly applied to plaintext in
classical cryptosystems to encode it prior to enciphering.  As an
example we see that
\[
\iota \circ \pi (\texttt{The cat in the hat.})
=
\texttt{THECATINTHEHAT}
\]
but strings in $\cA^*$ map injectively into $\texttt{ASCII}^*$:
\[
\pi \circ \iota \circ \pi (\texttt{THECATINTHEHAT})
=
\pi (\texttt{THECATINTHEHAT})
=
\texttt{THECATINTHEHAT}.
\]
The existence of the empty string $\varepsilon$ is crucial to the
definition of the map from \texttt{ASCII} to $\cA^*$, which shows that
the concept of a monoid, rather than a semigroup, is the correct one
for study of strings and the transformations which operate on them
(under the guise of encodings or ciphers).

In what follows, the domain and codomain of ciphers will be string
monoids or a subset $\cA^n$ of a string monoid $\cA^*$~(for block
ciphers). The latter ciphers may be extended naturally~(in what is
called ECB mode in Chapter~\ref{BlockCiphers}) to the submonoid
$(\cA^n)^*$ of $\cA^*$ on the larger alphabet $\cA^n$.  The concept of
a string monoid gives a useful framework for understanding ciphers.  A
first question to ask for a cipher whose domain is a string monoid is
whether that cipher is a monoid homomorphism.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Cryptosystems}

The notion of a cryptosystem or encryption scheme $\cE$ captures the
idea of a distinguished set of ciphers indexed over some key space
$\cK$:
\[
\cE
=
\{ E_K : \cM \to \cC \mid K \in \cK \}.
\]
To every enciphering key $K \in \cK$ there exists a deciphering key
$K'$ with deciphering map $D_{K'} : \cC \to \cM$.  Now $\cE$ should be
thought of as a pair of algorithms $E$ and $D$ that take inputs
$(K,M)$ and $(K',C)$, respectively.

We formalize this definition as follows.  First, we require a
collection of sets:
%%
\begin{center}
\begin{tabular}{c@{\ }c@{\ }lcc@{\ }c@{\ }l}
$\cA$  & = & plaintext alphabet & &
$\cA'$ & = & ciphertext alphabet \\
$\cM$  & = & plaintext space & &
$\cC$  & = & ciphertext space \\
$\cK$  & = & (plaintext) key space & &
$\cK'$ & = & (ciphertext) key space \\
\end{tabular}
\end{center}
%%
where $\cM$ is a subset of $\cA^*$, $\cC$ is a subset of $\cA'^*$, and
$\cK$ and $\cK'$ are finite sets. A \emph{cryptosystem} or
\emph{encryption scheme} is a pair $(E,D)$ of maps
\[
\begin{array}{l}
E: \cK \times \cM \to \cC, \\[4pt]
D: \cK'\! \times \cC \to \cM
\end{array}
\]
such that for each $K \in \cK$ there exists a $K' \in \cK'$ such that
\[
D(K',\, E(K,M))
=
M
\]
for all $M \in \cM$.

To recover our original notation, for a fixed $K$ we write the cipher
\[
E_K
=
E(K,\, \cdot{}) : \cM \to \cC
\]
and similarly
\[
D_{K'}
=
D(K',\, \cdot{}) : \cC \to \cM.
\]
With this notation the condition on $E$, $D$, $K$, and $K'$ is that
$D_{K'} \circ E_K$ is the identity map on $\cM$.  In this way, we
may express $E$ and $D$ as maps:
\[
\begin{array}{l}
E: \cK \to \Hom_{\tt Set}(\cM,\cC), \\[4pt]
D: \cK' \to \Hom_{\tt Set}(\cC,\cM).
\end{array}
\]

We will refer to $E_K$ as a \emph{cipher} and note that a cipher is
necessarily injective.  For many cryptosystems, there will exist a
unique deciphering key $K'$ associated to each enciphering key $K$.
A cryptosystem for which the deciphering key $K'$ equals $K$~(hence
$\cK = \cK'$) or for which $K'$ can be easily obtained from $K$, is
said to be \emph{symmetric}. If the deciphering key $K'$ associated to
$K$ is not easily computable from $K$, we say that the cryptosystem is
\emph{asymmetric} or a \emph{public key cryptosystem}.

A fundamental principle of~(symmetric key) cryptography is
\emph{Kerckhoffs' principle}, that the security of a cryptosystem does
not rest on the lack of knowledge of the cryptosystem $\cE = (E,D)$.
Instead, security should be based on the secrecy of the keys.

\begin{algorithm}[!htbp]
\input{algorithm/introduction/message-exchange-symmetric-key-cryptosystem.tex}
\caption{Message exchange protocol using a symmetric key cryptosystem.}
\label{alg:introduction:message_exchange_symmetric_key_cryptosystem}
\end{algorithm}

Recall that a \emph{protocol} is an algorithm, defined by a sequence
of steps, precisely specifying the actions of multiple parties in
order to achieve an objective.  As an example of a cryptographic
protocol,
Algorithm~\ref{alg:introduction:message_exchange_symmetric_key_cryptosystem}
describes the steps for message exchange using a symmetric key
cryptosystem. The difficulty of step~\ref{alg:secret_key_agreement}
was one of the fundamental obstructions to cryptography before the
advent of public key cryptography. Asymmetric cryptography provides an
elegant solution to the problem of distribution of private keys.
